package leetcode_jz_offer.day16_sort;

/**
 * 输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
 * 输入: [3,30,34,5,9]
 * 输出: "3033459"
 **/
//TODO:快排解法未写出
public class Num45_把数组排成最小的数 {
    /**
     * 比较当前遍历的字符x与下一个字符y拼接相加起来的值x+y与y+x的大小，x+y字符串对应小于y+x的话就不用交换位置，否则交换位置
     * 这里的字符串比较用到compareTo
     * @param nums
     * @return
     */
    public String minNumber(int[] nums) {
        //先将nums数组转为字符串数组
        String[] str=new String[nums.length];
        for (int i = 0; i < str.length; i++) {
            str[i]=String.valueOf(nums[i]);
        }
        for (int i = 0; i < str.length; i++) {
            for (int j = 0; j < str.length - 1; j++) {
                if((str[j]+str[j+1]).compareTo(str[j+1]+str[j])>0){//x+y>y+x// 比如 34,3 --> 343 > 334 所以两个数需要交换位置
                    String s=str[j];
                    str[j]=str[j+1];
                    str[j+1]=s;
                }
            }
        }
        //交换完毕字符串数组中就是需要的数组顺序结果，将他转为字符串
        StringBuilder sb=new StringBuilder();
        for (int i = 0; i < str.length; i++) {
            sb.append(str[i]);
        }
        return sb.toString();
    }
}
